import java.util.*;

public class LeetCode126 {
	class Solution {
		List<List<String>> result;
		List<Set<Integer>> map;
		List<List<Integer>> next;
		List<Integer> temp = new LinkedList<Integer>();
		int begin, end;
		List<String> wordList;

		public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
			wordList.add(beginWord);
//			Collections.sort(wordList);
			this.wordList = wordList;
			result = new LinkedList<List<String>>();
			map = new LinkedList<Set<Integer>>();
			next = new LinkedList<List<Integer>>();
			for (int i = 0; i < wordList.size(); i++) {
				map.add(new HashSet<Integer>());
				next.add(new LinkedList<Integer>());

			}
			Iterator<String> it1 = wordList.iterator();

			for (int i = 0; i < wordList.size(); i++) {
				Iterator<String> it2 = wordList.iterator();
				String string1 = it1.next();
				if (string1.equals(beginWord))
					begin = i;
				if (string1.equals(endWord))
					end = i;
				for (int j = 0; j < wordList.size(); j++) {
					
					String string2 = it2.next();
					if (match(string1, string2))
						map.get(i).add(j);
				}
			}
//			System.out.println(map);
//			Set<Integer> set =new HashSet<>();//����Ҫ
			boolean[] visited = new boolean[wordList.size()];
			Queue<Integer> queue = new LinkedList<Integer>();
			queue.add(begin);
			visited[begin] = true;
			while (!visited[end]) {
				while (!queue.isEmpty()) {
					Integer now = queue.poll();
					for (Integer integer : map.get(now))
						if (!visited[integer]) {
							temp.add(integer);
							next.get(now).add(integer);
//							System.out.println(now + " " + integer);
						}
				}
				queue.addAll(temp);
//				System.out.println(set);
				for (Integer integer : temp)
					visited[integer] = true;
				temp.clear();
			}

			getResult(begin);
			return result;
		}

		private boolean match(String string1, String string2) {
			int missCount = 0;
			for (int i = 0; i < string1.length(); i++)
				if (string1.charAt(i) != string2.charAt(i))
					missCount++;
			if (missCount == 1)
				return true;
			return false;
		}

		private LinkedList<String> changeInt2Str() {
			LinkedList<String> ls = new LinkedList<String>();
			for (Integer integer : temp) {
				ls.add(wordList.get(integer));
			}
			return ls;
		}

		private void getResult(int now) {
			temp.add(now);
			if (now == end) 
				result.add(changeInt2Str());
			else
				for (Integer integer : next.get(now))
					getResult(integer);
			((LinkedList<Integer>) temp).removeLast();
		}

	}

	public static void main(String[] args) {
		String beginWord = new String("hit");
		String endWord = new String("cog");
		List<String> list = new LinkedList<String>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));

		List<List<String>> result = new LeetCode126().new Solution().findLadders(beginWord, endWord, list);
		System.out.println(result);

	}
}
